////////////////////////////
// PAlib project template //
////////////////////////////

// Lines starting with two slashes are ignored by the compiler
// Basically you can use them to comment what are you doing
// In fact, this kind of lines are called comments :P

// Include PAlib so that you can use it
#include <PA9.h>
#include <fat.h>
const int pval = 256, pval2 = 512;
char bits[256][15], buffer[5000];
int nodes[512],nodefreq[512], nodechild1[512],nodechild2[512],nodeparent[512],bitlen[256];
int GenerateHuffmanCodes (int datafreq[256]);
int GenerateHuffmanCodes (int datafreq[256]){
	int c = 256,i = 0,s = 0,n = 0,fl1 = 0, fl2 = 0, l1 = 0,l2 = 0, i2 = 0;	
	//****Set everything to the starting values****
	for (i = 0;i < 512;i++){
		nodes[i] = -1;nodechild1[i] = -1;nodechild2[i] = -1;nodeparent[i] = -1;
	}		

	for (i = 0;i < 256;i++){
		nodes[i] = 0;nodefreq[i] = datafreq[i];	
	}
	//****Begin tree generation****	

	fl1 = 100000;fl2 = 100000;
	while(true){ 
		for (i = 0;i < 512;i++){ //Search through the tree, looking for the lowest node
			if ((nodes[i] != -1) && (nodefreq[i] < fl1)) {  
					
					//We've found a new low! Set the vars accordingly.					
					l1 = i; //Set l1 (The locater for the low) to i
					fl1 = nodefreq[i]; //Set fl1 to the new low
			}
			
		}
		if (fl1 == 100000) break; //If fl1 hasn't changed, get out of here		
		nodes[l1] = -1;	 //Tell it to ignore the latest node

		for (i = 0;i < 512;i++){ //Search through the tree, looking for the new lowest node
			if ((nodes[i] != -1) && (nodefreq[i] < fl2)) {  
					
					//We've found a new low! Set the vars accordingly.					
					l2 = i; //Set l2 (The locater for the low) to i
					fl2 = nodefreq[i]; //Set fl2 to the new low
			}
			
		}		
		

		if (fl2 != 100000) { //If fl1 has changed, merge two nodes of the tree and continue
			nodechild1[c] = l1;nodechild2[c] = l2; 
			nodefreq[c] = fl1 + fl2;
			nodes[l1] = -1;nodes[l2] = -1;
			nodes[c] = 0;		
			c++;
		}
		

		if (fl2 == 100000) break; //If fl2 hasn't changed, get me out of here
		fl1 = 100000;fl2 = 100000; // Reset fl1 and fl2
	}

	//Fill the nodeparent[] array	
	for (i = 0;i < 512;i++){
		if (nodechild1[i] != -1) nodeparent[nodechild1[i]] = i;
		if (nodechild2[i] != -1) nodeparent[nodechild2[i]] = i;	
	}

	//****Begin Prefix Generation****
	//Using that information, generate the prefix codes
	for (n = 0; n < 256;n++){
		i = n;c = 0;s = 0; //Start the process and default the variables
		while(true){
			c = nodeparent[i]; //Find the parent of the current node
			if (c == -1) break; 
			if (nodechild1[c] == i) bits[n][s] = 0; //If child #1 is the current node, set the bit to 0; otherwise set it to 1
			if (nodechild2[c] == i) bits[n][s] = 1;
			s++;i = c;	
			
		}
		bitlen[n] = s;	//Set the bitlength to the appropiate number
	}
	//****End prefix generation****
	return 0;
}
int main(){
	// Initialize PAlib
	PA_Init();
	PA_InitVBL();
	PA_InitText(1,0);	PA_OutputText(1,0,0,"Starting 0");	
	fatInitDefault();	
	int freq[256];
	char datain[1024],dataout[1024];
	int i = 0,i2 = 0,n = 0,c = 0,huff_buffer = 0, huff_buffer_len = 0,t = 0, dtpos = 0, totbits = 0,t2 = 0;
	int getbyte = 0;	
	int filelen = 0;
	int couldbe[256];
	FILE* testfile = fopen ("testfile.txt", "rb");	
	for (i = 0; i < 256; i++) freq[i] = 1;	
	while (true){
		getbyte = fgetc(testfile);
		if (getbyte == EOF) break;
		freq[getbyte]++;
		datain[filelen] = getbyte;
		filelen++;
		if (filelen == 1024) break;	
	}
	fclose(testfile);
	
	i2 = GenerateHuffmanCodes(freq);
	i = 0;
	//Encoding begins here
	huff_buffer = 0; huff_buffer_len = 0;	
	for (i = 0; i < filelen;i++){
		t = bitlen[datain[i]];
		if ((huff_buffer_len + t) > 7) {
			for (i2 = 0; i2 < t;i2++){			
				huff_buffer = huff_buffer + (bits[datain[i]][i2] << (huff_buffer_len + i2));
			}		
			t2 = (huff_buffer >> 8) << 8;
			dataout[dtpos] = huff_buffer - t2;
			dtpos++;
			huff_buffer >>= 8;
			totbits += t;			
			huff_buffer_len = (huff_buffer_len + t) - 8;		
		}		
		else{
			for (i2 = 0; i2 < t;i2++){			
				huff_buffer = huff_buffer + (bits[datain[i]][i2] << (huff_buffer_len + i2));
			}		
			huff_buffer_len += t;		
			totbits += t;
		}
	}	
	if (huff_buffer_len > 7) {		
		t2 = (huff_buffer >> 8) << 8;
		dataout[dtpos] = huff_buffer - t2;
		dtpos++;
		huff_buffer >>= 8;
	}		
	dataout[dtpos] = huff_buffer;
	dtpos++;
	for (i = 0; i < dtpos;i++){
		for (i2 = 0;i2 < 256;i2++) couldbe[i2] = 1;		
		n = 0;		
		while (true){
			t = dataout[i] & (1 << n)
		}
	}
	while(true){
		/*if (Pad.Held.B){		
			for (i2 = n;i2 < n + 22;i2++){
				PA_OutputText(1,0,i2 - n,"                          ");
				for (c = 0;c < bitlen[i2]; c++){
					if (bits[i2][c] == 1) PA_OutputText(1,bitlen[i2] - c,i2 - n,"1");
					else PA_OutputText(1,bitlen[i2] - c,i2 - n,"0");
				}				
			}
		
			if (Pad.Held.A)	{
				if (Pad.Held.Up) n--;		
				if (Pad.Held.Down) n++;
			}		
			else{
				if (Pad.Newpress.Up) n--;		
				if (Pad.Newpress.Down) n++;		
			}		
			if (n < 0) n = 0; if (n > 234) n = 234;
		}	
		else {
			if (Pad.Released.B) {
				for (i2 = n;i2 < n + 22;i2++){
					PA_OutputSimpleText(1,0,i2,"                 ");	
				}			
			}			
			if (Pad.Newpress.Up) i++;		
			if (Pad.Newpress.Down) i--;		
			if (i < 0) i = 0;
			if (i > (512)) i = (512);		
			PA_OutputText(1,0,0,"Number: %d      ",i);
			PA_OutputText(1,0,1,"  Parent: %d     ",nodeparent[i]);		
			PA_OutputText(1,0,2,"  Child 1 of parent: %d    ",nodechild1[nodeparent[i]]);
			PA_OutputText(1,0,3,"  Child 2 of parent: %d    ",nodechild2[nodeparent[i]]);
			PA_OutputText(1,0,4,"  Frequency of number: %d  ",nodefreq[i]);
			PA_OutputText(1,0,0,"Total Length: %d bits",totbits);
		}*/
		n = 0;		
		PA_OutputText(1,0,0,"Total Size (In bits): %d",totbits);		
		for (i = 1; i < n + 22;i++){
			PA_OutputText(1,0,i,"%d    %d    ",dataout[i], datain[i]);
		}
		PA_WaitForVBL();	
	}
	
}

